﻿/* * We are given an array of integers and a number S. Write a program to find if there exists a subset of the elements of the array that has a sum S. Example:
	arr={2, 1, 2, 4, 3, 5, 2, 6}, S=14  yes (1+2+5+6) */


using System;

class Subset
{
    static void Main()
    {
        uint N;
        int S;
       
        bool iProvided = false;
        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter a positive integer.");
            else iProvided = true;
            Console.Write("Enter N: ");
        } while (UInt32.TryParse(Console.ReadLine(), out N) == false || N < 1);
        
        iProvided = false; //reset iProvided
        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
            else iProvided = true;
            Console.Write("Enter S: ");
        } while (Int32.TryParse(Console.ReadLine(), out S) == false);

        iProvided = false; //reset iProvided
        int[] nums = new int[N];
        for (int i = 0; i < nums.Length; i++)
        {
            iProvided = false;
            do
            {

                if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
                else iProvided = true;
                Console.Write("Enter element {0}: ", i + 1);
            } while (Int32.TryParse(Console.ReadLine(), out nums[i]) == false);
        }

        int maxSets = (int)Math.Pow(2, nums.Length);
        bool found = false;
        int? currSum = null;
        for (int i = 1; i < maxSets; i++)
        {
                
            //Console.WriteLine(nums[i]);
            currSum = 0;
            for (int j = 1; j <= nums.Length; j++)
            {
                if (((i >> (j - 1)) & 1) == 1)
                {
                    currSum += nums[j - 1];
                }
            }
            if (currSum == S)
            {
                found = true;
            }
        }
        Console.WriteLine("----------------------------------");
        string arrElements = string.Join(", ", nums);
        string output = "A subset with the sum of " + S + " in the array with elements " + arrElements;
        if (found) output += " exist.";
        else output += " does not exist.";
        Console.WriteLine(output + "\r\n");

    }
}
